package leetcode.hot100;

import leetcode.tester.Tester;

import java.util.HashSet;
import java.util.Set;

/**
 * 3. 无重复字符的最长子串
 * https://leetcode.cn/problems/longest-substring-without-repeating-characters/?envType=study-plan-v2&envId=top-100-liked
 *
 * @author Liu Yicong
 * @date 2025/10/14
 */
public class Hot8SwinLengthOfLongestSubstring {
	public static void main(String[] args) {
		Object[][] inputs = {
				new Object[]{"abcabcbb"},
				new Object[]{"bbbbb"},
				new Object[]{"pwwkew"},
				new Object[]{"au"},
				new Object[]{"aab"},
		};
		Object[] outputs = {
				3, 1, 3, 2, 2
		};

		Tester.test(Tester.wrap(new Hot8SwinLengthOfLongestSubstring()::lengthOfLongestSubstring), inputs, outputs);
		Tester.test(Tester.wrap(new Hot8SwinLengthOfLongestSubstring()::lengthOfLongestSubstringSwin), inputs, outputs);
	}

	public int lengthOfLongestSubstring(String s) {
		int n = s.length();
		if (n < 2) {
			return n;
		}

		int l = 0, r = 0;
		int res = 0;
		Set<Character> set = new HashSet<>();

		while (r < n) {
			char c = s.charAt(r);
			if (!set.contains(c)) {
				set.add(c);
				res = Math.max(res, r - l + 1);
				r++;
			} else {
				set.remove(s.charAt(l++));
			}
		}
		return res;
	}

	/**
	 * 使用滑动窗口的方式
	 */
	public int lengthOfLongestSubstringSwin(String s) {
		int n = s.length();
		if (n < 2) {
			return n;
		}

		int res = 0, start = 0;
		for (int end = 1; end < n; end++) {
			String win = s.substring(start, end);
			String c = String.valueOf(s.charAt(end));
			if (win.contains(c)) {
				res = Math.max(res, end - start);
				start += win.indexOf(c) + 1;
			}
		}
		return Math.max(res, n - start);
	}

}
